package cn.edu.leetcode.动态规划;

import java.util.Scanner;

public class 完全平方数 {
    public static void main(String[] args) {
        System.out.println(numSquares(12));
    }

    public static int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            int s = (int) Math.sqrt(i);
            if (s*s == i) dp[i] = 1;

            for (int j = 1; j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + dp[i - j]); // 动态转移方程
            }
        }
        return dp[n];
    }

}
